package com.example.swordjava;


public class Test25 {

    public static void main(String[] args) {

        int[] a = {2, 3, 1, 0, 2, 5, 3};
    }

    class ListNode {
        ListNode next = null;
        int val;

        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 合并两个排序的链表
     * 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
     */

    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
        // write code here
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val < pHead2.val) {
                cur.next = pHead1;
                cur = cur.next;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                cur = cur.next;
                pHead2 = pHead2.next;
            }
        }
        if (pHead1 != null) {
            cur.next = pHead1;
        }
        if (pHead2 != null) cur.next = pHead2;
        return pre.next;
    }

    public ListNode Merge1(ListNode pHead1, ListNode pHead2) {
        // write code here
        if (pHead1 == null) return pHead2;
        if (pHead2 == null) return pHead1;


        if (pHead1.val <= pHead2.val) {
            pHead1.next = Merge1(pHead1.next, pHead2);
            return pHead1;
        } else {
            pHead2.next = Merge1(pHead1, pHead2.next);
            return pHead2;
        }
    }


}
